from typing import List


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        result = []
        pacific_records = set()
        atlantic_records = set()
        m = len(heights)
        n = len(heights[0])
        def dfs(x,y,records):
            records.add((x,y))
            for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                if nx < 0 or nx >= m: continue
                if ny < 0 or ny >= n: continue
                if (nx,ny) in records: continue
                if heights[x][y] > heights[nx][ny]: continue
                dfs(nx,ny,records)
        for i in range(0,m):
            dfs(i,0,pacific_records)
            dfs(i,n-1,atlantic_records)
        for j in range(0, n):
            dfs(0, j, pacific_records)
            dfs(m-1,j,atlantic_records)
        return list(pacific_records & atlantic_records)

if __name__ == '__main__':
    s = Solution()
    r = s.pacificAtlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]])
    print(r)